#include "regexp.h"

unsigned char parseEscapeChar(unsigned char c, const unsigned char *&s)
{
	switch(c)
	{
	case 'n': return '\n';
	case 't': return '\t';
	case 'r': return '\r';
	case 'x':
		{	int x1, x0=hexDigitToValue(s[0]);
			if (x0<0) throw("'\\x' sequence not finished.");
			x1=hexDigitToValue(s[1]);
			if (x1<0) throw("'\\x' sequence not finished.");
			s+=2;
			return x0*16+x1;
		}
	case '0': return '\0';
	case 0: throw("Excape character missing."); return 0;
	default: return c;
	}
}

namespace RE
{

#ifdef REGEXP_DEBUG
int findStateNr(Expr &e, State *p)
{	int i=0;
	if (p==0) return -1;
	FOREACH(List<State>, e.m_states, j)
	{	if (&*j==p) return i;
		i++;
	}
	_TECHO("Should not come here");
	return -2;
}

void printSM(Expr &e)
{
	printf("First state: %i\n", findStateNr(e,e.m_first));
	FOREACH(List<State>, e.m_states, j)
	{	printf("%p: State: %i useCount: %i\n", &*j, findStateNr(e,&*j), j->m_useCount);
		FOREACH(List<Transition>, *j, i)
	   printf("  %p: %s Next: %i \n", &*i,i->m_func->getName(), findStateNr(e,i->m_next));
	}
}

#endif

Transition::Transition(State *next, Func *func): m_next(next), m_func(func)
{
	if (next)
		next->m_useCount++;
}
void Transition::changeNext(State *next) {
	if (m_next)
		m_next->m_useCount--;
	m_next = next;
	if (next)
		next->m_useCount++;
}

void State::insert(int index, State *s_next, Func *f)
{	new (next(index)) Transition(s_next,f);
}

void Expr::parse()
{
	const unsigned char *s=m_expr;
	State *dummy;
	try
	{
		Transition::setFirst(m_first,convert(s,dummy, true));
	} catch(const char *err)
	{
		m_first=0;
		throw(err);
	}
	dummy->insert(0,0 );
	simplify();
}

Expr::Expr(unsigned char *str, int len, int mask):m_expr((char *)str,len), m_mask(mask) 
{
}

void Expr::simplify()
{
	if (!m_first) return;
	RE_DBG(printSM(*this);)
	// step 1: remove all useless states:
	// substep: move transition targets forward
	FOREACH(List<State>, m_states, s)
	{	for(List<Transition>::P e(&*s); !!*e;)
		{	Transition *se=&**e;
			State *next=se->m_next;
			if (next && next->isUseless())
			{	se->changeNext((*next)->m_next);
			}
			else e++;
		}
	}   
	RE_DBG(printSM(*this);)
	for(List<State>::P sp(&m_states); !!*sp;)
	{	if ((*sp)->isUseless()) 
		{	if (m_first==&**sp) {
				Transition::changeFirst(m_first,(**sp)->m_next);
			}
			State *next=(**sp)->m_next;
			if (next) next->m_useCount--;
			sp->removeone();
		}
		else sp++;
	}
	RE_DBG(printSM(*this);)
	// step 2: remove states that have one user
	FOREACH(List<State>, m_states, s)
	{	for(List<Transition>::P e(&*s); !!*e;)
		{	Transition *se=&**e;
			State *next=se->m_next;
			if (next && se->m_func==&funcAlways && next->m_useCount==1 )
			{	e->removeone(); // remove transition
				e->takeprependall(*next); // take over transitions
			}
			else e++;
		}
	}   
	for(List<State>::P sp(&m_states); !!*sp;)
	{	if (!**sp) 
			sp->removeone();
		else sp++;
	}
	RE_DBG(printSM(*this);)
}
void Expr::convertString(char *o, const char *i, const char *ie)
{
	for(;i!=ie;i++)
	{	
		switch (*i)
		{
		case '\n':  *(o++)='\\'; *(o++)='n'; break;
		case '\r':  *(o++)='\\'; *(o++)='r'; break;
		case '\t':  *(o++)='\\'; *(o++)='t'; break;
		case '\0':  *(o++)='\\'; *(o++)='0'; break;
		case '`':
		case '[':case ']':
		case '(':case ')':
		case '{':case '}':
		case '|':
		case '+':
		case '?':
		case '*':
		case '.':
		case '^':
		case '$':
		case '\\':  *(o++)='\\'; *(o++)= *i; break;
		default:		
			if (*(unsigned char *)i<' ' || *(unsigned char *)i == 255 ) {	sprintf(o,"\\x%02x", *i); o+=4; }
			else
				*(o++)=*i;
			break;
		}
	}
	*o=0;
}

Expr::Expr(Expr *left, String right, bool isLiteral): m_mask(left->m_mask)
{
	if (!isLiteral)
		m_expr=String(left->m_expr,right);
	else
	{	int ll=left->m_expr.length();
		String s((char *)left->m_expr, ll+4*right.length());
		convertString((char *)s+ll,(char *)right,(char *)right+right.length());
		m_expr=String((char *)s);
	}
	State *dummy;
	const unsigned char *e(m_expr);
	Transition::setFirst(m_first,convert(e,dummy, true));
	dummy->insert(0,0 );
	simplify();
}

Expr::~Expr() {}

struct Reg {	const unsigned char *m_beg; const unsigned char *m_end; Reg(const unsigned char *b, const unsigned char *e): m_beg(b), m_end(e) {} };

struct Pos {	const unsigned char *m_begPos, *m_endPos; };

class Context
{
protected:
	void updateChar();
public:
	bool m_isCI, m_isMulti;
	const unsigned char *m_beg, *m_end, *m_p, *m_start;
	List<const unsigned char *> m_regStack;
	List<Pos> m_posStack;
	List<Reg> m_regs;
	List<int> m_countStack;
	Context(const unsigned char *s, int len, int mask): m_beg(s), m_end(s+len), m_p(s),m_isCI(mask&1), m_isMulti(mask&2) {
		updateChar();
	}
	unsigned char m_c;
	bool m_isEnd;
	inline void nextChar() { m_p++; updateChar();}
	inline void prevChar() { m_p--; updateChar();}
	inline void changePos(const unsigned char *p) {	m_p=p; updateChar(); }
};

void Context::updateChar()
{
	m_isEnd = m_p>=m_end;
	if (m_isEnd)
		return;
	unsigned char c = *m_p;
	m_isEnd = (!m_isMulti && (c=='\r' || c=='\n'));
	m_c = m_isCI ? Expr::uncaps(c) : c;
}

struct Pair
{
	unsigned char m_first,m_last;
	Pair(unsigned char f, unsigned char l): m_first(f), m_last(l) {}
};

bool FuncAlways::doit(Context &c) {	return true;}
void FuncAlways::undo(Context &c) {	}
RE_DBG(const char *FuncAlways::getName() {	return "Always"; } )

FuncAlways funcAlways;

class CharFunc: public Func
{
public:
	void undo(Context &c)
	{	c.prevChar();
	}
};

static struct FuncAny: public CharFunc
{
	bool doit(Context &c)
	{	if (!c.m_isEnd) 
		{	c.nextChar();
			return true;
		}
		return false;
	}
	RE_DBG(const char *getName() {	return "Any"; } )
} funcAny;

struct FuncChar: public CharFunc
{
	unsigned char m_char;
	FuncChar(unsigned char c): m_char(c) {} 
	bool doit(Context &c)
	{	if (c.m_isEnd || c.m_c!=m_char) return false;
		c.nextChar();
		return true;
	}
	RE_DBG(const char *getName() {	return "Char"; } )
};

struct FuncRange: public CharFunc
{
	List<Pair> m_pairs;
	FuncRange(List<Pair> &t) {	m_pairs.take(t); }
	bool doit(Context &c)
	{	if (c.m_isEnd) return false;
		bool r=false;
		unsigned char ch=c.m_c;
		FOREACH(List<Pair>,m_pairs,i)
		{	r|= 
				ch>=(unsigned char)i->m_first &&
				ch<=(unsigned char)i->m_last;
		}
		if (r) c.nextChar();
		return r;
	}
	RE_DBG(const char *getName() {	return "Range"; } )
};

struct FuncRangeNot: public FuncRange
{
	FuncRangeNot(List<Pair> &t): FuncRange(t) {}
	bool doit(Context &c)
	{	if (c.m_isEnd) return false;
		unsigned char ch=c.m_c;
		bool r=true;
		FOREACH(List<Pair>,m_pairs,i)
		{	r&= 
				ch<i->m_first ||
				ch>i->m_last;
		}
		if (r) c.nextChar();
		return r;
	}
	RE_DBG(const char *getName() {	return "RangeNot"; } )
};

static struct FuncStoreReg: public Func
{
	bool doit(Context &c)
	{	new (c.m_regs) Reg(*c.m_regStack,c.m_p);
		c.m_regStack.removeone();
		return true;
	}
	void undo(Context &c)
	{	c.m_regStack.prepend(c.m_regs->m_beg);
		c.m_regs.removeone();
	}
	RE_DBG(const char *getName() {	return "StoreReg"; } )
} funcStoreReg;

struct FuncCountStart: public Func
{
	FuncCountStart() {}
	bool doit(Context &c)
	{	c.m_countStack.prepend(0);
		return true;
	}
	void undo(Context &c)
	{	c.m_countStack.removeone();
	}
};

struct FuncCountedRepeat: public Func
{
	int m_max;
	FuncCountedRepeat(int max): m_max(max) {}
	bool doit(Context &c)
	{	if (*c.m_countStack<m_max) 
		{	(*c.m_countStack)++;
			return true;
		}
		return false;
	}
	void undo(Context &c)
	{	(*c.m_countStack)--;
	}
};
struct FuncCountedFinish: public Func
{
	int m_min;
	Ptr<int>::Share m_count;
	FuncCountedFinish(int min): m_min(min) {}
	bool doit(Context &c)
	{	return *c.m_countStack>=m_min;
	}
};

static struct FuncAllocReg: public Func
{
	bool doit(Context &c)
	{	c.m_regStack.prepend(c.m_p);
		return true;
	}
	void undo(Context &c)
	{	c.m_regStack.removeone();
	}
	RE_DBG(const char *getName() {	return "AllocReg"; } )
} funcAllocReg;


static struct FuncStorePos: public Func
{
	bool doit(Context &c)
	{	c.m_posStack.prepend();
		c.m_posStack->m_begPos=c.m_p;
		return true;
	}
	void undo(Context &c)
	{	c.m_posStack.removeone();
	}
	RE_DBG(const char *getName() {	return "StorePos"; } )
} funcStorePos;

static struct FuncRestorePos: public Func
{
	bool doit(Context &c)
	{	c.m_posStack->m_endPos = c.m_p;
		c.changePos(c.m_posStack->m_begPos);
		return true;
	}
	void undo(Context &c)
	{	c.changePos(c.m_posStack->m_endPos);
	}
	RE_DBG(const char *getName() {	return "RestorePos"; } )
} funcRestorePos;


static struct FuncSetBegPos: public Func
{
	bool doit(Context &c)
	{	c.m_start = c.m_p;
	  return true;
	}
	RE_DBG(const char *getName() {	return "SetBegPos"; } )
} funcSetBegPos;

static struct FuncUndoSetBegPos: public Func
{
	void undo(Context &c)
	{	c.m_start = c.m_p;
	}
	RE_DBG(const char *getName() {	return "UndoSetBegPos"; } )
} funcUndoSetBegPos;

static struct FuncBegin: public Func
{
	bool doit(Context &c)
	{	return c.m_p==c.m_beg || ( !c.m_isMulti && c.m_p[-1]=='\n' );  
	}
	RE_DBG(const char *getName() {	return "Begin"; } )
} funcBegin;

static struct FuncEnd: public Func
{
	bool doit(Context &c)
	{	return c.m_isEnd;
	}
	RE_DBG(const char *getName() {	return "End"; } )
} funcEnd;

State *Expr::convert(const unsigned char *&s, State *&last, bool isFirst)
{
	State *first=orOpConvert(s,last, isFirst);
	if (s[0]=='|') 
	{	s++; 
		State *last2, *first2=convert(s, last2, isFirst); 
		first2->insert(0,first); 
		last->insert(0,last2);
		last=last2;
		return first2;
	}
	return first;
}

unsigned char Expr::getChar(const unsigned char *&s)
{
	unsigned char c=s[0];
	s++;
	if (c=='\\') 
	{	c=s[0];s++;
		c=parseEscapeChar(c,s);
	}
	else if (m_mask&1)
	{	c=uncaps(c);
	}      
	return c;
}

#define PARSE_END_MARKER(m) if (s[0]==0 || s[0]!=m) throw("Missing " #m "."); else s++;


State *Expr::orOpConvert(const unsigned char *&s, State *&last, bool isFirst)
{
	State *first;
	switch(s[0])
	{
	case 0:
	case '}':
	case ')':
	case '|':
		return last=new (m_states) State();
	case '[':
	  {	s++;
	    bool neg= s[0]=='^';
	    if (neg) s++;
	    int start=-1;
	    List<Pair> pairs;
	    while( s[0]!=']' && s[0]!=0 )
	    {	
	      unsigned char c=getChar(s);
	      if (s[0]=='-') 
	      {	start=(int)c; s++;
	      }
	      else
	      {	new (pairs) Pair(start<0?c:start,c); 
	        start=-1;
	      }       
	    }
	    PARSE_END_MARKER(']');
	    first=new (m_states) State();
	    last=new (m_states) State();
	    Func *f;
	    if (neg) 
	      f=new (m_funcs) FuncRangeNot(pairs);
	    else
	      f=new (m_funcs) FuncRange(pairs);
	    first->insert( 0, last, f);
	  } 
		break;
	case '{':
	  {	s++;
			if (s[0]=='?')
			{	s++;
				State *last2, *first2=convert(s,last2, false);
				first=new (m_states) State();
				last=new (m_states) State();
				if (isFirst)
				{	first->insert(0,first2,&funcUndoSetBegPos);
					last2->insert(0,last, &funcSetBegPos);
				}
				else
				{	first->insert(0,first2,&funcStorePos);
					last2->insert(0,last, &funcRestorePos);
				}
			}
			else {
				State *last2, *first2=convert(s,last2, isFirst);
				first=new (m_states) State();
				last=new (m_states) State();
				first->insert(0,first2);
				last2->insert(0,last);
//				first=convert(s,last, isFirst);
			}
	    PARSE_END_MARKER('}');
	  } 
		break;
	case '(':
	  {	s++; 
	    State *last2, *first2=convert(s,last2, isFirst);
	    first=new (m_states) State();
	  	last=new (m_states) State();
	  	first->insert(0,first2,&funcAllocReg);
	  	last2->insert(0,last, &funcStoreReg);
	   	PARSE_END_MARKER(')');
	  }
		break;
	case '.':
	  {	s++; 
	    first=new (m_states) State();
	    last=new (m_states) State();
	    first->insert( 0, last, &funcAny);
	  }
		break;
	case '^':
	  {	s++; 
	    first=new (m_states) State();
	    last=new (m_states) State();
	    first->insert(0, last, &funcBegin);
	  }
		break;
	case '$':
	  {	s++; 
	    first=new (m_states) State();
	    last=new (m_states) State();
	    first->insert(0, last, &funcEnd);
	  }
		break;
	default:
	  {	first=new (m_states) State();
		  last=new (m_states) State();
	    first->insert(0, last, new (m_funcs) FuncChar(getChar(s)));
	  }
		break;
	}
	switch(s[0])
	{
	case '?':
	  {	s++;
	    int i;
	    if (s[0]=='?') {s++;i=999;} else i=0; 
	    first->insert(i,last); 
	  }
		break;
	case '*':
	  {	s++;
	    State *n=new (m_states) State();
	    int i;
	    if (s[0]=='*') {s++;i=999;} else i=0; 
	    first->insert(i,n); 
	    last->insert(i, first ); 
	    last=n; 
	  }
		break;
	case '+':
	  {	s++;
	    State *n=new (m_states) State();
	    last->insert(0,n);
	    int i;
	    if (s[0]=='+') {s++;i=0;} else i=999; 
	    last->insert(i, first );
	    last=n;

	  }
		break;
	case '{':
	  {	if (s[1]=='*')
	  	{	s+=2;
	  		int min=0,max;
	  		Ptr<int>::Share pi;
		    State *nb=new (m_states) State();
		    State *ne=new (m_states) State();
		    int i;
			if (s[0]=='*') {s++;i=999;} else i=0; 
		    while (*s>='0'&&*s<='9') {	min=min*10+*s-'0'; s++; }
		    if (*s=='-')
		    {	s++;
		    	if (*s>='0'&&*s<='9')
		    	{	max=0;
		    		while (*s>='0'&&*s<='9') {	max=max*10+*s-'0'; s++; }
	    		}
	    		else
	    			max=1<<30;	
		    }
		    else
		    {	max=min;
		    }		    
		    Func *f;
	      f=new (m_funcs) FuncCountStart();
		    nb->insert(i, first, f );
	      f=new (m_funcs) FuncCountedFinish(min);
		    first->insert(i, ne, f );
	      f=new (m_funcs) FuncCountedRepeat(max);
		    last->insert(i, first, f ); 
		    first=nb;
		    last=ne;
		   	PARSE_END_MARKER('}');
			}
	  }
		break;
	default:
		break;
	}
	if( ! ( s[0]==0 || s[0]=='}' || s[0]==')' || s[0]=='|') ) 
	{	State *last2, *first2=orOpConvert(s,last2, false);
		last->insert(0,first2 );
		last=last2;
	}
 	return first;
}

void Expr::match(List<Match>::P matches, const unsigned char *s, int len, bool once)
{
	RE_DBG(printf("Matching:\r\n");)
	RE_DBG(printSM(*this);)  
#undef RE_DBG
#define RE_DBG(x)
	once = once || (m_mask&4);
	if (m_first==0)
		return;
	Context c(s,len,m_mask);
	const unsigned char *end=c.m_end;
	while(c.m_p<=end) {
		c.m_regs.erase();
		c.m_posStack.erase();
		c.m_countStack.erase();
		c.m_start=c.m_p;
		List<State::Iter> stack;
		stack.prepend(State::Iter(*m_first));
		for(;;) {
			RE_DBG(_TVAR(i,c.m_p-c.m_beg);)
			if ((*stack)->m_func->doit(c)) {
				RE_DBG(printf("Transition succeeded\n");)
				if (!(*stack)->m_next) { // end state is hit
					List<String> regs;
					FOREACH(List<Reg>,c.m_regs,i) {
						new (regs) String((char *)(i->m_beg),(int)(i->m_end-i->m_beg));
					}
					new (*matches) Match( c.m_start-s, c.m_p-c.m_start, regs);
					matches++; 
					if (once) 
						return;
					else if (c.m_p==c.m_start ) {
						if (c.m_p>=end)
							return;
						c.nextChar();
					}
					break;
				}
				RE_DBG(_TVAR(i,findStateNr(*this,(*stack)->m_next));)
				stack.prepend(State::Iter(*(*stack)->m_next));
			}
			else {
				RE_DBG(printf("Failed\n");)
				for (;;) {
					(*stack)++; //try next transition
					if (!!*stack) break;
					RE_DBG(printf("Back to previous state\n");)
					/*back to previous state*/ 
					stack.removeone();
					if(!stack) {
						RE_DBG(printf("Not found\n");) 
						if (c.m_p>=end)
							return;
						c.nextChar();
						goto stop;
					}/*stop if failed*/
					(*stack)->m_func->undo(c);
					//if(!*stack) {	c.nextChar(); break;}/*stop if failed*/
				}
			}
		}
		stop:;
	}
}

}
